package com.zdp.leetcodeMiddle;

import com.zdp.util.ListNode;

/*
* 题目描述：
* 反转从位置 m 到 n 的链表。请使用一趟扫描完成反转。
说明:
1 ≤ m ≤ n ≤ 链表长度。
示例:
输入: 1->2->3->4->5->NULL, m = 2, n = 4
输出: 1->4->3->2->5->NULL
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/reverse-linked-list-ii
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
* */
public class 反转链表Ⅱ_92 {
    public static void main(String[] args) {
        反转链表Ⅱ_92 demo = new 反转链表Ⅱ_92();
        ListNode head = ListNode.createListNode(4,5);
        ListNode listNode = demo.reverseBetween(head, 1, 2);
        listNode.soutList();
    }

    /*
    * 一趟扫描反转
    * 如果使用额外空间的话就格外轻松了
    * 利用头插法 将指定位置的链表反转（新建结点）
    * 记录指定位置俩表开头的前置结点 和  新链表的尾部结点
    * head1: 新建的链表  p:要反转的链表的后置结点
    * pre.next = head1.next;
    * tail.next = p;
    * */
    public ListNode reverseBetween(ListNode head, int m, int n) {

        if(m==n){
            return head;
        }
        ListNode pre = null;
        ListNode p = head;
        int count = 1;
        while(count<m){
            pre = p;
            p = p.next;
            count++;
        }
        // 头插法即可
        ListNode head1 = new ListNode(1);
        head1.next = null;
        ListNode tail = null;
        int n1 = m;
        while(m<=n){
            ListNode pp = new ListNode(p.val);
            p = p.next;
            pp.next = head1.next;
            head1.next = pp;
            if(n1==m){
                tail = pp;
            }
            m++;
        }
        // 将该段插入
        if(pre == null){
            tail.next = p;
            head = head1.next;
        }else{
            tail.next = p;
            pre.next = head1.next;
        }
        return head;
    }

    /*
    * 也可以不用额外空间来进行反转，要注意他们之间的连接关系
    * */
}
